import java.util.*;
import java.io.*;
/**
 *
 * @author Alex & Umit
 */
public class MyGraph {

    private Map<String,MySet> map;

    public MyGraph(){
        map = new HashMap();
    }

    public int size(){
        int count = 0;
        //iterate over all the keys
        Iterator it = map.keySet().iterator();
        while(it.hasNext()){
            //look the key up in the map
            MySet temp = map.get((String)it.next());
            //return the size of the entry at the corresponding key
            count += temp.size();
        }
        return count;
    }

    public void add(String origin, String destination){
        MySet set;
        if(map.containsKey(origin)){
            set = map.get(origin);
            set.add(destination);
        }
        if(!map.containsKey(origin)){
            set = new MySet();
            set.add(destination);
            map.put(origin, set);
        }
        if(!map.containsKey(destination)){
            set = new MySet();
            map.put(destination, set);
        }
    }

    public Iterator keys(){
        return map.keySet().iterator();
    }

    public static MyGraph readGraph(String fName){
        MyGraph res = new MyGraph();
        MySet set;

        String thisLine;
        StringTokenizer st;

        try{
            BufferedReader br = new BufferedReader(new FileReader(fName));
            while((thisLine = br.readLine()) != null){
                set = new MySet();
                st = new StringTokenizer(thisLine);
                String key = "";
                if(st.hasMoreTokens()){
                    key = st.nextToken();
                }
                while(st.hasMoreTokens()){
                    res.add(key, st.nextToken());
                }
            }

        }
        catch(IOException e){
            System.err.println("Error: " + e);
        }

        return res;
    }

    public MySet findConnections(MySet visited, MySet neighbours){
        MySet newNeighbours = new MySet();

        //Return all th node's we have visited when we have no more neighbors
        //to go through
        if(neighbours.isEmpty()){
            return visited;
        }
        else{
            Iterator it = neighbours.iterator();
            while(it.hasNext()){
                String temp = (String)it.next();
                //System.out.println(temp);
                newNeighbours.add(temp);
            }
            visited = visited.union(newNeighbours);
            neighbours = newNeighbours.difference(visited);
            return findConnections(visited, neighbours);
        }
    }

    public MySet connectedSet(String origin){
        MySet set = new MySet();
        MySet neighbours = map.get(origin);

        return findConnections(set, neighbours);
    }

    public boolean isConnected(String origin, String destination){
        MySet set = new MySet();
        set = connectedSet(origin);
        if(origin.equals(destination))
            return true;
        if(set.contains(destination)){
            return true;
        }
        else return false;
    }

    public boolean isStrongConnected(){
        Iterator it = keys();
        MySet res;

        //Check for all combination of nodes if they are connected in both directions
        while(it.hasNext()){
            String origin = (String)it.next();
            Iterator it2 = keys();
            while(it2.hasNext()){
                String destination = (String)it2.next();
                //If the origin is NOT connected to the destination or viceversa
                //return false
                if(!isConnected(origin, destination) || !isConnected(destination, origin)){
                    return false;
                }
            }
        }
        return true;
    }

    @Override
    public String toString(){
        return map.toString();
    }

}
